package cn.genmer.test.security.leetcode.medium;

import java.util.HashMap;

/**
 * 34. 在排序数组中查找元素的第一个和最后一个位置
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 *
 * 如果数组中不存在目标值 target，返回 [-1, -1]。
 *
 * 进阶：
 *
 * 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
 *
 * 我的题解: https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/34-zai-pai-xu-shu-zu-zhong-cha-zhao-yuan-hhad/
 */
public class NumbersStartAndEndIndex {

    /**
     * 看到提示的二分查找， 直接走题解
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange(int[] nums, int target) {
        if (nums.length == 0){
            return new int[] {-1, -1};
        }
        // 1. 查找元素开始位置
        int left =0;
        int right = nums.length-1;

       while (left < right){
            int mid = (left + right)/2;
            // 查找target第一次出现的下标
            if (nums[mid] >= target) right = mid;
            else left = mid + 1;
       }
       // 查找失败
       if (nums[right] != target) return new int[] {-1, -1};
       // 记录开始下标值
        int first = right;
        // 2. 查找元素结束位置
        left =0;
        right = nums.length-1;
        while (left < right){
            int mid = (left + right)/2;
            // 查找target第一次出现的下标
            if (nums[mid] <= target) left = mid;
            else right = mid - 1;
        }
        return  new int[]{first, right};
    }

    public static int[] binarySearch(int[] nums, int target, int start, int end){
        int mid = start + (end - start)/2;
        int result1 = -1;
        int result2 = -1;
            if (target == nums[mid]){
                if (result1 == -1){
                    result1 = mid;
                    result2 = mid;
                }
                for (int i=mid+1; i< end; i++){
                    if (nums[i] != target){
                        return new int[] {result1, result2};
                    }
                }
            }


        if (target > nums[mid]){
            return binarySearch(nums,target,start,mid);
        } else {
            return binarySearch(nums,target,mid,end);
        }
    }

    /**
     * 最早写通过的版本，看着才超过10%的人
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange1(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int END_INDEX = 99;
        for (int i=0; i< nums.length; i++){
            if (map.containsKey(target)){
                if (nums[i] != target){
                    return new int[] {map.get(target), map.get(END_INDEX)};
                }
            }
            if (nums[i] == target){
                if (!map.containsKey(target)){
                    map.put(target, i);
                    map.put(END_INDEX, i);
                }
                map.put(END_INDEX, i);
            }
        }
        int default1 = map.get(target) == null ? -1 : map.get(target);
        int default2 = map.get(END_INDEX) == null ? -1 : map.get(END_INDEX);
        return new int[] {default1,default2};
    }
}
